class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        int inf = INT_MAX / 2;
        vector<vector<pair<int,int> > > edges(n);
        vector<vector<int> > visited(n,vector<int>(2,0));
        vector<int> dist(n,inf);
        
        for(auto& vc : redEdges){
            edges[vc[0]].push_back({vc[1],0});
        }
        for(auto& vc : blueEdges){
            edges[vc[0]].push_back({vc[1],1});
        }
        
        dist[0] = 0;
        queue<vector<int> > qe;
        qe.push({0,0,0});
        qe.push({0,0,1});
        
        
        while(!qe.empty()){
            auto v = qe.front();
            qe.pop();
            int from = v[0];
            int distance = v[1];
            int col = v[2];
            
            for(auto& u : edges[from]){
                if(u.second != col && !visited[u.first][u.second]){
                    dist[u.first] = min(dist[u.first],distance+1);
                    qe.push({u.first,distance+1,u.second});
                    visited[u.first][u.second] = 1;
                }
            }
        
        }
        
        for(int i = 0;i < n;i++){
            if(dist[i] >= inf){
                dist[i] = -1;
            }
        }
        
        return dist;
    }
};
